package org.example.day05;

import java.util.Scanner;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * <p>  算法工程师小明面对着这样一个问题，需要将通信用的信道分配给尽量多的用户： </p> <p>  <br> </p> <p>  信道的条件及分配规则如下： </p> <p>  1)     所有信道都有属性：”阶”。阶为r的信道的容量为2^r比特； </p> <p>  2)     所有用户需要传输的数据量都一样：D比特； </p> <p>  3)     一个用户可以分配多个信道，但每个信道只能分配给一个用户； </p> <p>  4)     只有当分配给一个用户的所有信道的容量和&gt;=D，用户才能传输数据； </p> <p>  <br> </p> <p>  给出一组信道资源，最多可以为多少用户传输数据？ </p>
 * <p>
 * 算法工程师小明面对着这样一个问题，需要将通信用的信道分配给尽量多的用户：
 * <p>
 * 信道的条件及分配规则如下：
 * 1)     所有信道都有属性：”阶”。阶为r的信道的容量为2^r比特；
 * 2)     所有用户需要传输的数据量都一样：D比特；
 * 3)     一个用户可以分配多个信道，但每个信道只能分配给一个用户；
 * 4)     只有当分配给一个用户的所有信道的容量和>=D，用户才能传输数据；
 * <p>
 * 给出一组信道资源，最多可以为多少用户传输数据？
 * @date 2024/3/11 15:22
 */
public class test083 {

    /**
     * 计算最多可以供多少用户传输数据的函数。
     *
     * @param R        最大阶数
     * @param channels 每种信道的数量数组
     * @param D        单个用户需要的数据量
     * @return 可以服务的最大用户数
     */
    public static int maxUsers(int R, int[] channels, int D) {
        int userCount = 0; // 初始化能够服务的用户数为0
        long remainingChannels = 0; // 计算所有信道的总容量
        for (int i = 0; i <= R; i++) {
            remainingChannels += channels[i] * (1 << i); // 1 << i等价于2的i次方
        }

        while (remainingChannels >= D) { // 如果剩余的信道容量仍然可以满足至少一个用户的需求
            int requiredD = D; // 对于当前用户，记录还需要多少容量
            for (int i = R; i >= 0; i--) { // 从最大阶开始尝试分配
                if (requiredD <= 0) {
                    break; // 如果当前用户的需求已经满足，则退出循环
                }
                int channelCapacity = 1 << i; // 当前阶信道的容量
                while (channels[i] > 0 && requiredD - channelCapacity >= 0) {
                    requiredD -= channelCapacity; // 减少用户的剩余需求
                    channels[i]--; // 减少该阶信道的数量
                    remainingChannels -= channelCapacity; // 更新剩余信道容量
                }
            }

            // 尝试使用最小的信道来补充不足
            for (int i = 0; i <= R; i++) {
                while (channels[i] > 0 && requiredD > 0) {
                    requiredD -= 1 << i;
                    channels[i]--;
                    remainingChannels -= 1 << i;
                    if (requiredD <= 0) { // 如果需求已满足
                        break;
                    }
                }
            }

            if (requiredD <= 0) { // 如果这轮循环后用户需求被满足
                userCount++; // 增加已服务的用户数
            } else { // 如果还有剩余需求，但信道不足以满足任何用户
                break; // 退出循环
            }
        }

        return userCount;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取最大阶数
        int R = scanner.nextInt();
        // 读取每种信道的数量
        int[] channels = new int[R + 1];
        for (int i = 0; i <= R; i++) {
            channels[i] = scanner.nextInt();
        }
        // 读取单个用户需要的数据量
        int D = scanner.nextInt();

        // 计算最多可以供多少用户传输数据
        int result = maxUsers(R, channels, D);
        // 输出结果
        System.out.println(result);
    }
}

